/*
 ------------------------------------------------------------------------------
 Copyright (C) 2006-2007 Team Blur.

 This file is part of the Quantum Engine source code.

 The Quantum Engine source code is free software; you can redistribute it and/or
 modify it under the terms of the GNU General Public License as published by
 the Free Software Foundation; either version 2 of the License, or (at your
 option) any later version.

 The Quantum Engine source code is distributed in the hope that it will be useful,
 but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
 or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License for
 more details.

 You should have received a copy of the GNU General Public License along with
 the Quantum Engine source code; if not, write to the Free Software Foundation, Inc.,
 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
 ------------------------------------------------------------------------------
*/


#include "cm_local.h"


typedef struct {
	bool		isPoint;
	int			contentMask;

	odVec3		point;

	odBounds	bounds;
	odVec3		offsets[8];

	int			contents;
} contentsWork_t;


/*
 ==================
 CM_BrushContents
 ==================
*/
static void CM_BrushContents (contentsWork_t *cw, cmBrush_t *brush){

	cmBrushSide_t	*side;
	odPlane			*plane;
	float			dist;
	int				i;

	// Test the brush bounds
	if (!brush->bounds.IntersectsBounds(cw->bounds))
		return;

	// The first six planes are the axial planes, so we only need to test the
	// remainder
	for (i = 6; i < brush->numSides; i++){
		side = &brush->sides[i];
		plane = side->plane;

		dist = plane->Distance(cw->point);

		// Adjust the plane distance appropriately for the box
		if (plane->type < PLANETYPE_NONAXIAL)
			dist += cw->offsets[plane->signBits][plane->type];
		else
			dist += cw->offsets[plane->signBits].Dot(plane->normal);

		// If completely in front of face, no intersection
		if (dist > 0.0f)
			return;
	}

	// Inside this brush
	cw->contents |= brush->material->contentFlags;
}

/*
 ==================
 CM_SurfaceContents
 ==================
*/
static void CM_SurfaceContents (contentsWork_t *cw, cmSurface_t *surface){

	cmSurfaceFacet_t	*facet;
	odPlane				*plane;
	odVec3				normal;
	float				dist;
	int					i, j;

	// Test the surface bounds
	if (!surface->bounds.IntersectsBounds(cw->bounds))
		return;

	// Test the surface facets
	for (i = 0, facet = surface->facets; i < surface->numFacets; i++, facet++){
		plane = &surface->planes[facet->facetPlane];

		dist = plane->Distance(cw->point);

		// Adjust the plane distance appropriately for the box
		if (plane->type < PLANETYPE_NONAXIAL)
			dist += cw->offsets[plane->signBits][plane->type];
		else
			dist += cw->offsets[plane->signBits].Dot(plane->normal);

		// If completely in front of face, no intersection
		if (dist > 0.0f)
			continue;

		for (j = 0; j < facet->numBorders; j++){
			plane = &surface->planes[facet->borderPlanes[j]];

			if (facet->borderInward & BIT(j)){
				normal = -plane->normal;
				dist = -plane->dist;
			}
			else {
				normal = plane->normal;
				dist = plane->dist;
			}

			// This works even though the plane might be flipped because the
			// box is centered
			dist += M_Fabs(cw->offsets[plane->signBits].Dot(normal));

			if (cw->point.Dot(normal) - dist > 0.0f)
				break;
		}

		if (j != facet->numBorders)
			continue;

		// Inside this surface facet
		cw->contents |= surface->material->contentFlags;

		return;
	}
}

/*
 ==================
 CM_LeafContents
 ==================
*/
static void CM_LeafContents (contentsWork_t *cw, cmLeaf_t *leaf){

	cmBrush_t	*brush;
	cmSurface_t	*surface;
	int			i, num;

	cm_stats.leafContents++;	// Optimize counter

	// Test against all brushes in the leaf
	for (i = 0; i < leaf->numLeafBrushes; i++){
		num = cm.leafBrushes[leaf->firstLeafBrush + i];
		brush = &cm.brushes[num];

		if (brush->contentsCount == cm.contentsCount)
			continue;		// Already checked this brush in another leaf
		brush->contentsCount = cm.contentsCount;

		if (!(brush->material->contentFlags & cw->contentMask))
			continue;		// Doesn't have the contents we're looking for

		if ((brush->material->contentFlags & cw->contents) == brush->material->contentFlags)
			continue;		// Doesn't have any new contents

		cm_stats.brushContents++;		// Optimize counter

		// Test against the brush
		CM_BrushContents(cw, brush);
	}

	// No point test against surfaces
	if (cw->isPoint)
		return;

	// Test against all surfaces in the leaf
	if (cm_skipSurfaces->integerValue)
		return;

	for (i = 0; i < leaf->numLeafSurfaces; i++){
		num = cm.leafSurfaces[leaf->firstLeafSurface + i];
		surface = cm.surfaces[num];

		if (!surface)
			continue;		// No collision data

		if (surface->contentsCount == cm.contentsCount)
			continue;		// Already checked this surface in another leaf
		surface->contentsCount = cm.contentsCount;

		if (!(surface->material->contentFlags & cw->contentMask))
			continue;		// Doesn't have the contents we're looking for

		if ((surface->material->contentFlags & cw->contents) == surface->material->contentFlags)
			continue;		// Doesn't have any new contents

		if (surface->type == ST_PATCH)
			cm_stats.patchContents++;		// Optimize counter
		if (surface->type == ST_TRISOUP)
			cm_stats.trisoupContents++;		// Optimize counter

		// Test against the surface
		CM_SurfaceContents(cw, surface);
	}
}

/*
 ==================
 CM_InlineModelContents
 ==================
*/
static void CM_InlineModelContents (contentsWork_t *cw, cmInlineModel_t *model){

	// If the model has multiple brushes and/or surfaces
	if (model->leaf.numLeafBrushes + model->leaf.numLeafSurfaces > 1){
		// If it doesn't have the contents we're looking for, ignore it
		if (!(model->leaf.contentFlags & cw->contentMask))
			return;

		// If it doesn't have any new contents, ignore it
		if ((model->leaf.contentFlags & cw->contents) == model->leaf.contentFlags)
			return;

		// If completely outside the model bounds, ignore it
		if (!model->bounds.IntersectsBounds(cw->bounds))
			return;
	}

	// Test against all brushes and surfaces in the model
	CM_LeafContents(cw, &model->leaf);
}

/*
 ==================
 CM_StaticModelContents
 ==================
*/
static void CM_StaticModelContents (contentsWork_t *cw, cmStaticModel_t *model){

	cmSurface_t	*surface;
	int			i;

	// No point test against surfaces
	if (cw->isPoint)
		return;

	// If the model has multiple surfaces
	if (model->numSurfaces > 1){
		// If it doesn't have the contents we're looking for, ignore it
		if (!(model->contentFlags & cw->contentMask))
			return;

		// If it doesn't have any new contents, ignore it
		if ((model->contentFlags & cw->contents) == model->contentFlags)
			return;

		// If completely outside the model bounds, ignore it
		if (!model->bounds.IntersectsBounds(cw->bounds))
			return;
	}

	// Test against all surfaces in the model
	if (cm_skipSurfaces->integerValue)
		return;

	for (i = 0, surface = model->surfaces; i < model->numSurfaces; i++, surface++){
		if (!(surface->material->contentFlags & cw->contentMask))
			continue;		// Doesn't have the contents we're looking for

		if ((surface->material->contentFlags & cw->contents) == surface->material->contentFlags)
			continue;		// Doesn't have any new contents

		cm_stats.meshContents++;		// Optimize counter

		// Test against the surface
		CM_SurfaceContents(cw, surface);
	}
}

/*
 ==================
 CM_DynamicModelContents
 ==================
*/
static void CM_DynamicModelContents (contentsWork_t *cw, cmDynamicModel_t *model){

	cmTriangleSurface_t	*surface;
	int					i, j;

	// No point test against surfaces
	if (cw->isPoint)
		return;

	// If the model has multiple surfaces
	if (model->numSurfaces > 1){
		// If it doesn't have the contents we're looking for, ignore it
		if (!(model->contentFlags & cw->contentMask))
			return;

		// If it doesn't have any new contents, ignore it
		if ((model->contentFlags & cw->contents) == model->contentFlags)
			return;

		// If completely outside the model bounds, ignore it
		if (!model->bounds.IntersectsBounds(cw->bounds))
			return;
	}

	// Test against all surfaces in the model
	if (cm_skipSurfaces->integerValue)
		return;

	for (i = 0, surface = model->surfaces; i < model->numSurfaces; i++, surface++){
		if (!(surface->material->contentFlags & cw->contentMask))
			continue;		// Doesn't have the contents we're looking for

		if ((surface->material->contentFlags & cw->contents) == surface->material->contentFlags)
			continue;		// Doesn't have any new contents

		cm_stats.meshContents++;		// Optimize counter

		// Test the surface bounds
		if (!surface->bounds.IntersectsBounds(cw->bounds))
			continue;

		// Test the surface vertices
		for (j = 0; j < surface->numVertices; j++){
			if (cw->bounds.ContainsPoint(surface->transformedXyz[j]))
				break;
		}

		if (j == surface->numVertices)
			continue;

		// Inside this surface
		cw->contents |= surface->material->contentFlags;
	}
}

/*
 ==================
 CM_WorldPointContents
 ==================
*/
static void CM_WorldPointContents (contentsWork_t *cw, int num){

	cmNode_t	*node;
	cmLeaf_t	*leaf;
	int			side;

	while (1){
		// If < 0, we are in a leaf node
		if (num < 0){
			leaf = &cm.leafs[-1 - num];

			if (!(leaf->contentFlags & cw->contentMask))
				return;			// Doesn't have the contents we're looking for

			if ((leaf->contentFlags & cw->contents) == leaf->contentFlags)
				return;			// Doesn't have any new contents

			// Test against all brushes and surfaces in the leaf
			CM_LeafContents(cw, leaf);
			return;
		}

		// Find which side of the node we are on
		node = &cm.nodes[num];

		side = node->plane->PointOnSide(cw->point);

		// Go down the appropriate side
		if (side == PLANESIDE_FRONT)
			num = node->children[0];
		else
			num = node->children[1];
	}
}

/*
 ==================
 CM_WorldBoxContents
 ==================
*/
static void CM_WorldBoxContents (contentsWork_t *cw, int num){

	cmNode_t	*node;
	cmLeaf_t	*leaf;
	int			side;

	// If < 0, we are in a leaf node
	if (num < 0){
		leaf = &cm.leafs[-1 - num];

		if (!(leaf->contentFlags & cw->contentMask))
			return;			// Doesn't have the contents we're looking for

		if ((leaf->contentFlags & cw->contents) == leaf->contentFlags)
			return;			// Doesn't have any new contents

		// Test against all brushes and surfaces in the leaf
		CM_LeafContents(cw, leaf);
		return;
	}

	// Find which side of the node we are on
	node = &cm.nodes[num];

	side = node->plane->BoundsOnSide(cw->bounds);

	// Go down the appropriate sides
	if (side == PLANESIDE_FRONT){
		CM_WorldBoxContents(cw, node->children[0]);
		return;
	}
	if (side == PLANESIDE_BACK){
		CM_WorldBoxContents(cw, node->children[1]);
		return;
	}

	CM_WorldBoxContents(cw, node->children[0]);
	CM_WorldBoxContents(cw, node->children[1]);
}

/*
 ==================
 CM_Contents
 ==================
*/
int CM_Contents (const odVec3 &point, const odBounds &bounds, int contentMask, clipModel_t *model, const odVec3 &modelOrigin, const odMat3 &modelAxis){

	contentsWork_t	cw;
	odBounds		size;
	odVec3			offset;
	int				i;

	if (!cm.loaded)
		Com_Error(false, "CM_Contents: map not loaded");

	cm.contentsCount++;		// For multi-check avoidance

	// Fill in the default contents
	cw.contents = 0;

	cw.contentMask = contentMask;

	// Adjust so that the bounds are always symetric, which avoids some
	// complications with plane expanding of rotated models
	offset = bounds.GetCenter();

	if (offset.IsCleared()){
		cw.point = point;

		size = bounds;
	}
	else {
		cw.point = point + offset;

		size = bounds - offset;
	}

	// Transform into local space
	if (modelAxis.IsIdentity())
		cw.point -= modelOrigin;
	else
		modelAxis.ProjectVector(cw.point - modelOrigin, cw.point);

	// Check for point special case
	if (size.IsZeroed())
		cw.isPoint = true;
	else
		cw.isPoint = false;

	// Expand size for epsilons
	if (cw.isPoint)
		size.Expand(CM_CLIP_EPSILON);
	else
		size.Expand(CM_BOX_EPSILON);

	// Calculate bounds
	for (i = 0; i < 3; i++){
		cw.bounds[0][i] = cw.point[i] + size[0][i];
		cw.bounds[1][i] = cw.point[i] + size[1][i];
	}

	// Set offsets to appropriate corners from origin
	cw.offsets[0].Set(size[0][0], size[0][1], size[0][2]);
	cw.offsets[1].Set(size[1][0], size[0][1], size[0][2]);
	cw.offsets[2].Set(size[0][0], size[1][1], size[0][2]);
	cw.offsets[3].Set(size[1][0], size[1][1], size[0][2]);
	cw.offsets[4].Set(size[0][0], size[0][1], size[1][2]);
	cw.offsets[5].Set(size[1][0], size[0][1], size[1][2]);
	cw.offsets[6].Set(size[0][0], size[1][1], size[1][2]);
	cw.offsets[7].Set(size[1][0], size[1][1], size[1][2]);

	cm_stats.contents++;	// Optimize counter

	// Test against the model or world
	if (model){
		if (cm_skipModels->integerValue)
			return 0;

		switch (model->type){
		case CLIP_MODEL_INLINE:
			CM_InlineModelContents(&cw, (cmInlineModel_t *)model->data);
			break;
		case CLIP_MODEL_STATIC:
			CM_StaticModelContents(&cw, (cmStaticModel_t *)model->data);
			break;
		case CLIP_MODEL_DYNAMIC:
			CM_DynamicModelContents(&cw, (cmDynamicModel_t *)model->data);
			break;
		}
	}
	else {
		if (cw.isPoint)
			CM_WorldPointContents(&cw, 0);
		else
			CM_WorldBoxContents(&cw, 0);
	}

	return cw.contents;
}
